﻿/**
 * 该模块提供实现 IMap(TKey, TValue) 接口的有序 Map 集合。
 * License: BSD
 * Authors: Lucifer (786325481@QQ.com)
 * Copyright: Copyright (C) 2008 Lucifer. All rights reserved.
 */

module system.collections.TreeMap;

import system.collections.IEnumerable;
import system.collections.IEnumerator;
import system.collections.ICollection;
import system.collections.IMap;
import system.collections.IComparer;
import system.collections.Comparer;
import system.collections.IEqualityComparer;
import system.collections.EqualityComparer;
import system.collections.Pair;
import system.collections.TreeSet;

import system.collections.Exception;

import system.Exception;
import system.Traits;

/**
 * 表示按键排序的键-值对的有序集合。
 * TreeMap(TKey, TValue) 泛型类是检索运算复杂度为 O(log n) 的二叉搜索树(红黑树)，其中 n 是字典中的元素数。
 */
public class TreeMap(TKey, TValue) : IEnumerable!(Pair!(TKey, TValue)), ICollection!(Pair!(TKey, TValue)), IMap!(TKey, TValue)
{
	private KeyCollection theKeys;
	private ValueCollection theValues;
	private TreeSet!(Pair!(TKey, TValue)) theSet;

	/**
	 * 初始化 TreeMap(TKey, TValue) 类的一个新实例，
	 * 该实例为空并使用指定的 IComparer(Pair!(TKey, TValue)) 实现来比较键。
	 * Params:
	 *		comparer = 在比较键时要使用的 IComparer(Pair!(TKey, TValue)) 实现；
	 *					或者为 null ，表示为键类型使用默认的 DefaultComparer(Pair!(TKey, TValue))。
	 */
	public this(IComparer!(Pair!(TKey, TValue)) comparer = DefaultComparer!(Pair!(TKey, TValue)).getInstance())
	in
	{
		assert(comparer !is null);
	}
	body
	{
		theSet = new TreeSet!(Pair!(TKey, TValue))(comparer);
	}

	/**
	 * 初始化 TreeMap(TKey, TValue) 类的新实例，
	 * 该实例包含从指定的 IMap(TKey, TValue) 中复制的元素，
	 * 并使用指定的 IComparer(Pair!(TKey, TValue)) 实现来比较键。
	 * Params:
	 *		map = 它的元素被复制到新的 TreeMap(TKey, TValue) 中。
	 *  	comparer = 在比较键时要使用的 IComparer(Pair!(TKey, TValue)) 实现；
	 *					或者为 null ，表示为键类型使用默认的 DefaultComparer(Pair!(TKey, TValue))。
	 * Throws:
	 * 		AssertError，当 map 为 null 时。
	 */
	public this(IMap!(TKey, TValue) map, IComparer!(Pair!(TKey, TValue)) comparer = DefaultComparer!(Pair!(TKey, TValue)).getInstance())
	in
	{
		assert(map !is null);
		assert(comparer !is null);
	}
	body
	{
		theSet = new TreeSet!(Pair!(TKey, TValue))(comparer);
		foreach(pair; map)
		{
			theSet.add(pair);
		}
	}

	/*
	 * 实现 IMap(TKey, TValue) 接口。
	 */

	/**
	 * 将带有指定键和值的元素添加到 TreeMap(TKey, TValue) 中。
	 * Params:
	 *		key = 要添加的元素的键。
	 *		value = 要添加的元素的值。对于引用类型，该值可以为 null 。
	 * Throws:
	 *		AssertError，当 key 为 null 时。
	 * Comments:
	 *		键不能为 null ，但如果值类型 TValue 为引用类型，该值则可以为 null 。
	 *		此方法的运算复杂度为 O(log n)。
	 */
	public final void add(TKey key, TValue value)
	in
	{
		static if(IsReferenceType!(TKey))
		{
			assert(key !is null);
		}
	}
	body
	{
		theSet.add(Pair!(TKey, TValue)(key, value));
	}

	/**
	 * 从 TreeMap(TKey, TValue) 中移除带有指定键的元素。
	 * Params:
	 *		key = 要移除的元素的键。
	 * Returns:
	 *		如果该元素已成功移除，则为 true；否则为 false。
	 *	 	如果在 TreeMap(TKey, TValue) 中没有找到 key，此方法也会返回 false。
	 * Throws:
	 *		AssertError，当 key 为 null 时。
	 * Comments:
	 *		如果 TreeMap(TKey, TValue) 不包含带有指定键的元素，则 TreeMap(TKey, TValue) 保持不变。不引发异常。
	 *		此方法的运算复杂度为 O(log n)。
	 */
	public final bool remove(TKey key)
	in
	{
		static if(IsReferenceType!(TKey))
		{
			assert(key !is null);
		}
	}
	body
	{
		return theSet.remove(Pair!(TKey, TValue)(key, TValue.init));
	}

	/**
	 * 检测 TreeMap(TKey, TValue) 是否包含具有指定键的元素。
	 * Params:
	 * 		key = 要在 TreeMap(TKey, TValue) 中定位的键。
	 * Returns:
	 *		如果 TreeMap(TKey, TValue) 包含具有指定键的元素，则为 true；否则为 false。
	 * Throws:
	 *		AssertError，当 key 为 null 时。
	 * Comments:
	 *		此方法的运算复杂度为 O(log n)。
	 */
	public final bool containsKey(TKey key)
	in
	{
		static if(IsReferenceType!(TKey))
		{
			assert(key !is null);
		}
	}
	body
	{
		return theSet.contains(Pair!(TKey, TValue)(key, TValue.init));
	}

    /**
	 * 检测 TreeMap(TKey, TValue) 是否包含具有指定值的元素。
	 * Params:
	 *		value = 要在 TreeMap(TKey, TValue) 中定位的值。对于引用类型，该值可以为 null 。
	 * Returns:
	 *		如果 TreeMap(TKey, TValue) 包含具有指定值的元素，则为 true；否则为 false。
	 * Comments:
	 *		此方法通过对值类型 TValue 使用默认的相等比较器 DefaultEqualityComparer(TValue) 来确定是否相等。
	 * 		此方法执行线性搜索，因此平均执行时间与 count 属性成比例。即，此方法的运算复杂度为 O(n)，其中 n 为 count。
	 */
	public final bool containsValue(TValue value)
	{
		auto comparer = DefaultEqualityComparer!(TValue).getInstance();
		static if(IsReferenceType!(TValue))
		{
			if(value is null)
			{
				foreach(item; theSet)
				{
					if(item.value is null)
						return true;
				}
			}
			else
			{
				foreach(item; theSet)
				{
					if(comparer.equals(item.value, value))
					return true;
				}
			}
		}
		else
		{
			foreach(item; theSet)
			{
				if(comparer.equals(item.value, value))
				return true;
			}
		}
		return false;
	}

	/**
	 * 获取与指定的键相关联的值。
	 * Params:
	 *		key = 要获取的值的键。
	 *		value = 当此方法返回时，如果找到指定键，则返回与该键相关联的值；
	 *				 否则，将返回 value 参数的类型的默认值。
	 * Returns:
	 *		如果 TreeMap(TKey, TValue) 包含具有指定键的元素，则为 true；否则为 false。
	 * Throws:
	 *		AssertError，当 key 为 null 时。
	 * Comments:
	 *		此方法融合了 containsKey 和 opIndex 的功能。
	 *		此方法的运算复杂度为 O(log n)。
	 */
	public final bool tryGetValue(TKey key, out TValue value)
	in
	{
		static if(IsReferenceType!(TKey))
		{
			assert(key !is null);
		}
	}
	body
	{
		auto node = theSet.theTree.findNode(Pair!(TKey, TValue)(key, TValue.init));
		if(node is null)
		{
			value = TValue.init;
			return false;
		}

		value = node.value.value;
		return true;
	}

	/**
	 * 获取包含 TreeMap(TKey, TValue) 中的键的集合。
	 * Comments:
	 *		TreeMap(TKey, TValue).keys 属性返回此类型的一个实例，
	 *		该实例包含此 TreeMap(TKey, TValue) 中的所有键。
	 *		TreeMap(TKey, TValue).KeyCollection 中键的顺序与 TreeMap(TKey, TValue) 中元素的顺序相同，
	 *		与 TreeMap(TKey, TValue).values 属性所返回的 TreeMap(TKey, TValue).ValueCollection 中的关联值的顺序也相同。
	 *
	 *		TreeMap(TKey, TValue).KeyCollection 不是静态副本；
	 *		相反，TreeMap(TKey, TValue).KeyCollection 反向引用原始 TreeMap(TKey, TValue) 中的键。
	 *		因此，对 TreeMap(TKey, TValue) 的更改将继续反映到 TreeMap(TKey, TValue).KeyCollection 中。
	 *
	 *		获取此属性的值的运算复杂度为 O(1)。
	 */
	public final KeyCollection keys()
	{
		if(theKeys is null)
		{
			theKeys = new KeyCollection();
		}
		return theKeys;
	}

	/**
	 * 获取包含 TreeMap(TKey, TValue) 中的值的集合。
	 * Comments:
	 *		TreeMap(TKey, TValue).ValueCollection 中的值根据 comparer 属性进行排序，
	 * 		并且与 keys 属性所返回的 TreeMap(TKey, TValue).KeyCollection 中的关联键具有相同的顺序。
	 *
	 * 		返回的 TreeMap(TKey, TValue).ValueCollection 不是静态副本；
	 * 		相反，TreeMap(TKey, TValue).ValueCollection 反向引用原始 TreeMap(TKey, TValue) 中的值。
	 * 		因此，对 TreeMap(TKey, TValue) 的更改将继续反映到 TreeMap(TKey, TValue).ValueCollection 中。
	 *
	 *		获取此属性的值的运算复杂度为 O(1)。
	 */
	public final ValueCollection values()
	{
		if(theValues is null)
		{
			theValues = new ValueCollection();
		}
		return theValues;
	}

	/**
	 * 获取与指定的键相关联的值。
	 * Params:
	 * 		key = 要获取的值的键。
	 * Throws:
	 *		Error，当 key 为 null 时。
	 *		KeyNotFoundException，当已检索该属性，并且集合中不存在 key。
	 */
	public final TValue opIndex(TKey key)
	in
	{
		static if(IsReferenceType!(TKey))
		{
			assert(key !is null);
		}
	}
	body
	{
		auto node = theSet.theTree.findNode(Pair!(TKey, TValue)(key, TValue.init));
		if(node is null)
			throw new KeyNotFoundException();
		return node.value.value;
	}

	/**
	 * 设置与指定的键相关联的值。
	 * Params:
	 * 		key = 要设置的值的键。
	 *		value = 要设置的值。
	 * Throws:
	 *		Error，当 key 为 null 时。
	 */
	public final void opIndexAssign(TValue value, TKey key)
	in
	{
		static if(IsReferenceType!(TKey))
		{
			assert(key !is null);
		}
	}
	body
	{
		auto node = theSet.theTree.findNode(Pair!(TKey, TValue)(key, TValue.init));
		if(node is null)
		{
			theSet.add(Pair!(TKey, TValue)(key, value));
		}
		else
		{
			node.value = Pair!(TKey, TValue)(key, value);
			theSet.theVersion++;
		}
	}

	/*
	 * 实现 ICollection(Pair!(TKey, TValue)) 接口。
	 */

	/**
	 * 将指定的键-值对添加到 TreeMap(TKey, TValue) 中。
	 * Params:
	 *		pair = 要加入的键-值对。
	 * Throws:
	 *		ArgumentException，当 TreeMap(TKey, TValue) 已存在这样的键-值对时。
	 *		Error，当键-值对的 key 为 null 时。
	 */
	public final bool add(Pair!(TKey, TValue) pair)
	in
	{
		static if(IsReferenceType!(TKey))
		{
			assert(pair.key !is null);
		}
	}
	body
	{
		return theSet.add(pair);
	}

	/**
	 * 检测此 TreeMap(TKey, TValue) 是否为空。
	 */
	public final bool isEmpty()
	{
		return theSet.isEmpty();
	}

	/**
	 * 获取此 TreeMap(TKey, TValue) 所包含的键-值对数量。
	 */
	public final int count()
	{
		return theSet.count();
	}

	/**
	 * 检测此 TreeMap(TKey, TValue) 是否只读。
	 * Returns:
	 *		false。
	 */
	public final bool isReadOnly()
	{
		return false;
	}

	/**
	 * 清空此 TreeMap(TKey, TValue) 。
	 * Comments:
	 *		count 属性被设置为 0，并且集合中的元素对其他对象的引用也被释放。
	 *		此方法的运算复杂度为 O(1)，因为内部数据结构的根只为垃圾回收而释放。
	 */
	public final void clear()
	{
		theSet.clear();
	}

	/**
	 * 从此 TreeMap(TKey, TValue) 中移除指定的键-值对。
	 * Params:
	 * 		pair = 要移除的键-值对。
	 * Returns:
	 *		如果已从 TreeMap(TKey, TValue) 中成功移除 pair，则为 true；否则为 false。
	 *		如果在 TreeMap(TKey, TValue) 中没有找到 pair，此方法也会返回 false。
	 * Throws:
	 *		Error，当键-值对的 key 为 null 时。
	 * Comments:
	 *		此方法通过先使用键的比较器，然后使用值的 DefaultEqualityComparer(TValue) 来确定是否相等。
	 *		此方法的运算复杂度为 O(log n)。
	 */
	public final bool remove(Pair!(TKey, TValue) pair)
	in
	{
		static if(IsReferenceType!(TKey))
		{
			assert(pair.key !is null);
		}
	}
	body
	{
		auto node = theSet.theTree.findNode(pair);
		if(node !is null && DefaultEqualityComparer!(TValue).getInstance.equals(node.value.value, pair.value))
		{
			theSet.remove(pair);
			return true;
		}
		return false;
	}

	/**
	 * 确定 TreeMap(TKey, TValue) 是否包含特定的键和值。
	 * Params:
	 *		pair = 要检测的键-值对。
	 * Returns:
	 *		如果在 TreeMap(TKey, TValue) 中找到 pair，则为 true；否则为 false。
	 * Throws:
	 *		Error，当键-值对的 key 为 null 时。
	 * Comments:
	 *		此方法通过先使用键的比较器，然后使用值的 DefaultEqualityComparer(TValue) 来确定是否相等。
	 *		此方法的运算复杂度为 O(log n)。
	 */
	public final bool contains(Pair!(TKey, TValue) pair)
	in
	{
		static if(IsReferenceType!(TKey))
		{
			assert(pair.key !is null);
		}
	}
	body
	{
		auto node = theSet.theTree.findNode(pair);

		if(node is null)
		{
			return false;
		}

		static if(IsReferenceType!(TValue))
		{
			if(pair.value is null)
			{
				return node.value.value is null;
			}
		}

		return DefaultEqualityComparer!(TValue).getInstance().equals(node.value.value, pair.value);
	}

	/**
	 * 将 TreeMap(TKey, TValue) 的元素复制到指定的 Pai(TKey, TValue) 结构的数组中。
	 * Params:
	 * 		array = 它是从当前 TreeMap(TKey, TValue) 中复制的元素的目标。
	 * Throws:
	 *		Error，当 array 为 null 或 array 长度小于此 TreeMap 的 count 时。
	 * Comments:
	 *		此方法的运算复杂度为 O(n) 。
	 */
	public final void toArray(Pair!(TKey, TValue)[] array)
	in
	{
		assert( array !is null );
		assert( array.length >= this.count() );
	}
	body
	{
		theSet.toArray(array);
	}

	/*
	 * 实现 IEnumerable(Pair!(TKey, TValue)) 接口。
	 */

	public final IEnumerator!(Pair!(TKey, TValue)) getEnumerator()
	{
		return theSet.getEnumerator();
	}

	public final int opApply (int delegate (ref Pair!(TKey, TValue) value) dg)
	{
		return theSet.opApply(dg);
	}

	public final int opApply(int delegate(ref TKey, ref TValue) dg)
	{
		auto scope iterator = theSet.getEnumerator();
		int result = 0;
		while(iterator.moveNext())
		{
			auto pair = iterator.current();
			auto key = pair.key;
			auto value = pair.value;
			if( (result = dg(key, value)) != 0 )
				break;
		}
		return result;
	}

	/**
	 * 返回此 Map 所使用的比较器。
	 */
	public final IComparer!(Pair!(TKey, TValue)) comparer()
	{
		return theSet.comparer();
	}

	/**
	 * 表示 TreeMap(TKey, TValue) 中键的集合。
	 * Comments:
	 *		TreeMap(TKey, TValue).keys 属性返回此类型的一个实例，
	 *		该实例包含此 TreeMap(TKey, TValue) 中的所有键。
	 *		TreeMap(TKey, TValue).KeyCollection 中键的顺序与 TreeMap(TKey, TValue) 中元素的顺序相同，
	 *		与 TreeMap(TKey, TValue).values 属性所返回的 TreeMap(TKey, TValue).ValueCollection 中的关联值的顺序也相同。
	 *
	 *		TreeMap(TKey, TValue).KeyCollection 不是静态副本；
	 *		相反，TreeMap(TKey, TValue).KeyCollection 反向引用原始 TreeMap(TKey, TValue) 中的键。
	 *		因此，对 TreeMap(TKey, TValue) 的更改将继续反映到 TreeMap(TKey, TValue).KeyCollection 中。
	 */
    public class KeyCollection : IEnumerable!(TKey), ICollection!(TKey)
	{
		public this()
		{
		}

		/*
		 * 实现 IEnumerable(TKey) 接口。
		 */

		public IEnumerator!(TKey) getEnumerator()
		{
		    return new KeysEnumerator();
		}

		public int opApply (int delegate (ref TKey value) dg)
		{
			auto scope enumerator = new KeysEnumerator();
			int result = 0;
			while( enumerator.moveNext() )
			{
				auto value = enumerator.current();
				if( (result = dg(value) ) != 0 )
					break;
			}
			return result;
		}

		public class KeysEnumerator : IEnumerator!(TKey)
		{
			private IEnumerator!(Pair!(TKey, TValue)) theIterator;

			public this()
			{
				theIterator = theSet.getEnumerator();
			}

			public bool moveNext()
			{
				return theIterator.moveNext();
			}

			public TKey current()
			{
				return theIterator.current.key;
			}

			public void reset()
			{
				theIterator.reset();
			}
		}

		/*
		 * 实现 ICollection(TKey) 接口。
		 */

		public bool isEmpty()
		{
			return theSet.isEmpty();
		}

		public int count()
		{
			return theSet.count();
		}

		public bool add(TKey key)
		{
			throw new NotSupportedException();
			return false;
		}

		public bool isReadOnly()
		{
			return true;
		}

		public void clear()
		{
			throw new NotSupportedException();
		}

		public bool remove(TKey key)
		{
			throw new NotSupportedException();
			return false;
		}

		public bool contains(TKey key)
		{
			return theSet.contains(Pair!(TKey, TValue)(key, TValue.init));
		}

		public void toArray(TKey[] array)
		in
		{
			assert( array !is null );
			assert( array.length >= this.count(), "The length of array is too small." );
		}
		body
		{
			auto index = 0;
			foreach(pair; theSet)
			{
				array[index++] = pair.key;
			}
		}
	}

	/**
	 * 获取包含 TreeMap(TKey, TValue) 中的值的集合。
	 * TreeMap(TKey, TValue).ValueCollection 中的值根据 comparer 属性进行排序，
	 * 并且与 keys 属性所返回的 TreeMap(TKey, TValue).KeyCollection 中的关联键具有相同的顺序。
	 *
	 * 返回的 TreeMap(TKey, TValue).ValueCollection 不是静态副本；
	 * 相反，TreeMap(TKey, TValue).ValueCollection 反向引用原始 TreeMap(TKey, TValue) 中的值。
	 * 因此，对 TreeMap(TKey, TValue) 的更改将继续反映到 TreeMap(TKey, TValue).ValueCollection 中。
	 */
	public class ValueCollection : IEnumerable!(TValue), ICollection!(TValue)
	{
		public this()
		{
		}

		/*
		 * 实现 IEnumerable(TValue) 接口。
		 */

		public IEnumerator!(TValue) getEnumerator()
		{
			return new ValuesEnumerator();
		}

		public int opApply (int delegate (ref TValue value) dg)
		{
			auto scope enumerator = new ValuesEnumerator();
			int result = 0;
			while( enumerator.moveNext() )
			{
				auto value = enumerator.current();
				if( (result = dg(value) ) != 0 )
					break;
			}
			return result;
		}

		public class ValuesEnumerator : IEnumerator!(TValue)
		{
			private IEnumerator!(Pair!(TKey, TValue)) theIterator;

			public this()
			{
				theIterator = theSet.getEnumerator();
			}

			public bool moveNext()
			{
				return theIterator.moveNext();
			}

			public TValue current()
			{
				return theIterator.current.value;
			}

			public void reset()
			{
				theIterator.reset();
			}
		}

		/*
		 * 实现 ICollection(TValue) 接口。
		 */

		public bool isEmpty()
		{
			return theSet.isEmpty();
		}

		public int count()
		{
			return theSet.count();
		}

		public bool add(TValue value)
		{
			throw new NotSupportedException();
			return false;
		}

		public bool isReadOnly()
		{
			return true;
		}

		public void clear()
		{
			throw new NotSupportedException();
		}

		public bool remove(TValue value)
		{
			throw new NotSupportedException();
			return false;
		}

		public bool contains(TValue value)
		{
			auto comparer = DefaultEqualityComparer!(TValue).getInstance();
			foreach(item; theSet)
			{
				if(comparer.equals(item.value, value))
					return true;
			}
			return false;
		}

		public void toArray(TValue[] array)
		in
		{
			assert( array !is null );
			assert( array.length >= this.count(), "The length of array is too small." );
		}
		body
		{
			auto index = 0;
			foreach(pair; theSet)
			{
				array[index++] = pair.value;
			}
		}
	}
}

unittest
{
	class TestTreeMap
	{
		void testCtor()
		{
			auto map = new TreeMap!(int, int)();

			assert( map !is null );
			assert( map.count == 0 );
			assert( map.isEmpty() );

			try
			{
				map = new TreeMap!(int, int)(cast(IMap!(int, int))null);
			}
			catch(Error e)
			{
				assert(true);
			}

			try
			{
				map = new TreeMap!(int,int)(cast(IComparer!(Pair!(int, int)))null);
			}
			catch(Error e)
			{
				assert(true);
			}

			map = new TreeMap!(int,int)();

			map.add(1, 1);
			map.add(2, 2);
			map.add(3, 3);

			auto map2 = new TreeMap!(int,int)(map);

			assert(map2.count == 3);
			assert(map2[1] == 1);
			assert(map2[2] == 2);
			assert(map2[3] == 3);
		}

		void testAdd()
		{
			auto map = new TreeMap!(int, string)();

			map.add(1, "A");

			assert(map.count == 1);
			assert(!map.isEmpty());

			try
			{
				map.add(1, "A");
			}
			catch(ArgumentException e)
			{
				assert(true);
			}

			map.add(0, null);
			map.add(2, null);

			assert(map[0] is null);
			assert(map[1] is "A");
			assert(map[2] is null);

			auto map2 = new TreeMap!(string,int)();

			try
			{
				map2.add(null, 1);
			}
			catch(Error e)
			{
				assert(true);
			}
		}

		void testIndexer()
		{
			auto map = new TreeMap!(int,int)();
			try
			{
				assert(map[0] == 0);
			}
			catch(KeyNotFoundException e)
			{
				assert(true);
			}

			map[0] = 1;

			assert(map.count == 1);
			assert(map[0] == 1);
		}

		void testRemove()
		{
			auto map = new TreeMap!(int, int)();

			map.add(1, 10);

			assert(map.remove(1));
			assert(map.count == 0);
			assert(!map.remove(1));
		}

		void testTryGetValue()
		{
			auto map = new TreeMap!(int, string)();

			string str;
			
			assert(!map.tryGetValue(0, str));
			assert(str is null);

			map.add(0, "Test");

			assert(map.tryGetValue(0, str));
			assert(str is "Test");

			assert(!map.tryGetValue(1, str));
			assert(str is null);
		}

		void testClear()
		{
			auto map = new TreeMap!(int, int)();

			map.add(1, 1);
			map.add(2, 2);
			map.add(3, 3);

			assert(map.containsKey(1));
			assert(map.containsValue(1));

			map.clear();

			assert(map.count == 0);
			assert(map.isEmpty());
		}

		void testEnumerator()
		{
			auto map = new TreeMap!(int, string)();

			map.add(1, "A");
			map.add(2, "B");
			map.add(3, "C");

			auto iterator = map.getEnumerator();

			assert(iterator.moveNext());
			assert(iterator.current.value == "A");
			assert(iterator.moveNext());
			assert(iterator.current.value == "B");
			assert(iterator.moveNext());
			assert(iterator.current.value == "C");
			assert(!iterator.moveNext());

			map.add(4, "D");

			try
			{
				iterator.reset();
			}
			catch(InvalidOperationException e)
			{
				assert(true);
			}
		}

		void testKeys()
		{
			auto map = new TreeMap!(int, string)();
			map.add(1, "A");
			auto collection = map.keys;
			
			assert(collection.count == 1);
			
			try
			{
				collection.add(2);
			}
			catch(NotSupportedException e)
			{
				assert(true);
			}

			try
			{
				collection.clear();
			}
			catch(NotSupportedException e)
			{
				assert(true);
			}

			try
			{
				collection.remove(1);
			}
			catch(NotSupportedException e)
			{
				assert(true);
			}

			assert(collection.contains(1));
		}

		void testKeysEnumerator()
		{
			auto map = new TreeMap!(int, string)();
			
			map.add(1, "A");
			map.add(2, "B");
			map.add(3, "C");

			auto iterator = map.keys.getEnumerator();

			assert(iterator.moveNext());
			assert(iterator.current == 1);
			assert(iterator.moveNext());
			assert(iterator.current == 2);
			assert(iterator.moveNext());
			assert(iterator.current == 3);
			assert(!iterator.moveNext());

			map.add(4, "D");

			try
			{
				iterator.reset();
			}
			catch(InvalidOperationException e)
			{
				//throw e;
				assert(true);
			}
		}

		void testValues()
		{
			auto map = new TreeMap!(int, string)();
			map.add(1, "A");
			auto collection = map.values;
			
			assert(collection.count == 1);
			
			try
			{
				collection.add("B");
			}
			catch(NotSupportedException e)
			{
				assert(true);
			}

			try
			{
				collection.clear();
			}
			catch(NotSupportedException e)
			{
				assert(true);
			}

			try
			{
				collection.remove("A");
			}
			catch(NotSupportedException e)
			{
				assert(true);
			}

			assert(collection.contains("A"));
		}

		void testValuesEnumerator()
		{
			auto map = new TreeMap!(int, string)();
			
			map.add(1, "A");
			map.add(2, "B");
			map.add(3, "C");

			auto iterator = map.values.getEnumerator();

			assert(iterator.moveNext());
			assert(iterator.current == "A");
			assert(iterator.moveNext());
			assert(iterator.current == "B");
			assert(iterator.moveNext());
			assert(iterator.current == "C");
			assert(!iterator.moveNext());

			map.add(4, "D");

			try
			{
				iterator.reset();
			}
			catch(InvalidOperationException e)
			{
				//throw e;
				assert(true);
			}
		}

		void testForEach()
		{
			auto map = new TreeMap!(int, string)();
			auto intArray = [1, 2, 3, 4, 5];
			auto strArray = ["A", "B", "C", "D", "E"];

			map.add(1, "A");
			map.add(2, "B");
			map.add(3, "C");
			map.add(4, "D");
			map.add(5, "E");

			auto index = 0;

			foreach(item; map)
			{
				assert(item.key == intArray[index]);
				assert(item.value == strArray[index]);
				index++;
			}

			index = 0;

			foreach(key, value; map)
			{
				assert(key == intArray[index]);
				assert(value == strArray[index]);
				index++;
			}
		}
	}

	auto test = new TestTreeMap();

	test.testCtor();
	test.testAdd();
	test.testIndexer();
	test.testRemove();
	test.testTryGetValue();
	test.testClear();
	test.testEnumerator();
	test.testKeys();
	test.testKeysEnumerator();
	test.testValues();
	test.testValuesEnumerator();
	test.testForEach();
}